package com.ntd.study.algorithm.sort.impl;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.ObjectUtil;
import com.ntd.study.algorithm.sort.Sort;

import java.util.HashMap;
import java.util.function.BiFunction;

/**
 * 计数排序
 *
 * @author liuwenju
 * @date 2021/4/30 17:34
 */
public class SortCount<T> implements Sort<T> {

    private Sort<T> sort = new SortFast<>();
    private BiFunction<T,T, Boolean> sortFunction;

    @Override
    public T[] sort(T[] arrays, BiFunction<T, T, Boolean> sort) {
        this.sortFunction = sort;
        try {
            return this.sort(arrays);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return arrays;
    }

    public T[] sort(T[] arr) throws Exception {
        return countingSort(arr);
    }

    private T[] countingSort(T[] arr) {
        HashMap<T, Integer> bucketLenHashMap = new HashMap<>(arr.length);

        for (T value : arr) {
            Integer integer = bucketLenHashMap.get(value);
            if (ObjectUtil.isNull(integer)) {
                integer = 0;
            }
            bucketLenHashMap.put(value, integer + 1);
        }

        T[] sort = this.sort.sort(ArrayUtil.removeNull(bucketLenHashMap.keySet().toArray(arr)), sortFunction);

        int sortedIndex = 0;
        for (T t : sort) {
            Integer integer = bucketLenHashMap.get(t);
            while (integer > 0) {
                arr[sortedIndex++] = t;
                bucketLenHashMap.put(t, --integer);
            }
        }

        return arr;
    }
}
